package jianzhiOffer;
//剑指 Offer 51. 数组中的逆序对
public class Num51_reversePairs {
    public int reversePairs(int[] nums) {
        return reversePairs(nums,0,nums.length-1);

    }
//传入一个数组，就可以求出逆序对的个数
    private int reversePairs(int[] nums, int l, int r) {
        if (l >= r){
            return 0;
        }
        int mid = l+((r-l)>>1);
        //先求出左区间的逆序对
        int left = reversePairs(nums,l,mid);
        //在求出右区间的逆序对
        int right = reversePairs(nums,mid+1,r);

        if (nums[mid] > nums[mid+1]){
            //排序好的左右区间还存在逆序对
            return merge(nums,l,mid,r)+left+right;
        }
        return left+right;



    }

    /**
     * 合并两个有序区间
     * @param nums
     * @param l
     * @param r
     * @return
     */

    private int merge(int[] nums, int l, int mid,int r) {
        int aux[] = new int[l-r+1];
        //逆序对个数
        int ret = 0;
        for (int i = 0; i < aux.length; i++) {
            aux[i] = nums[l+i];
        }
        int i = l;
        int j = mid+1;
        for (int k = l; k <=r ; k++) {
            if (i > mid){
                //左区间已经走完
                nums[k] = aux[j-l];
                j++;
            }else if (j > r){
                //右区间已经走完
                nums[k] = aux[i-l];
                i++;
            }else if (aux[i-l]<=aux[j - l]){
                //不构成逆序对
                nums[k] = aux[i - l];
                i++;


            }else {
                ret+=(mid-i)+1;
                nums[k] = aux[j - l];
                j++;


            }
        }
        return ret;
    }

}
